home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / list / RCS / List.man,v < prev    next >
Text File  |  1989-12-14  |  11KB  |  431 lines
  1. head     1.2;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @@;
  7.  
  8.  
  9. 1.2
  10. date     89.12.14.12.27.51;  author shirriff;  state Exp;
  11. branches ;
  12. next     1.1;
  13.  
  14. 1.1
  15. date     89.12.14.12.26.29;  author shirriff;  state Exp;
  16. branches ;
  17. next     ;
  18.  
  19.  
  20. desc
  21. @@
  22.  
  23.  
  24. 1.2
  25. log
  26. @*** empty log message ***
  27. @
  28. text
  29. @' $Header: /sprite/src/lib/c/list/RCS/List.man,v 1.1 89/12/14 12:26:29 shirriff Exp Locker: shirriff $ SPRITE (Berkeley)
  30. .so \*(]ltmac.sprite
  31. .HS List lib
  32. .BS
  33. .SH NAME
  34. List \- overview of circular linked list routines.
  35. .SH SYNOPSIS
  36. .nf
  37. \fB#include <list.h>\fR
  38. .sp
  39. \fBList_Init\fR(\fIheaderPtr\fP)
  40. \fBList_InitElement\fR(\fIitemPtr\fP)
  41. \fBList_Insert\fR(\fIitemPtr\fP, \fIdestPtr\fP)
  42. \fBList_ListInsert\fR(\fIheaderPtr\fP, \fIdestPtr\fP)
  43. \fBList_Remove\fR(\fIitemPtr\fP)
  44. \fBList_Move\fR(\fIitemPtr\fP, \fIdestPtr\fP)
  45. .sp
  46. \fBLIST_AFTER\fR(\fIitemPtr\fP)
  47. \fBLIST_BEFORE\fR(\fIitemPtr\fP)
  48. \fBLIST_ATFRONT\fR(\fIheaderPtr\fP)
  49. \fBLIST_ATREAR\fR(\fIheaderPtr\fP)
  50. .sp
  51. \fBLIST_FORALL\fR(\fIheaderPtr\fP, \fIitemPtr\fP)
  52. .sp
  53. \fBList_IsEmpty\fR\fR\fB(\fIheaderPtr\fP)
  54. \fBList_IsAtEnd\fR(\fIheaderPtr\fP, \fIitemPtr\fP)
  55. \fBList_First\fR\fR\fB(\fIheaderPtr\fP)
  56. \fBList_Last\fR\fR\fB(\fIheaderPtr\fP)
  57. \fBList_Prev\fR\fR\fB(\fIitemPtr\fP)
  58. \fBList_Next\fR\fR\fB(\fIitemPtr\fP)
  59. .SH ARGUMENTS
  60. .AS List_Links *headerPtr in
  61. .AP List_Links *headerPtr in
  62. Pointer to the header of a list.
  63. .AP List_Links *itemPtr in 
  64. Pointer to a member of a list (possibly the header).
  65. .AP List_Links *destPtr in 
  66. Pointer to the member after which to insert or move another member.
  67. .BE
  68.  
  69. .SH INTRODUCTION
  70. .PP
  71. The \fBList_\fR\ routines define the ``list'' abstraction, 
  72. which enables one to link
  73. together arbitrary data structures.  Lists are doubly-linked and
  74. circular.  A list contains a header followed by its real members, if
  75. any.  (An empty list therefore consists of a single element, the
  76. header,  whose \fInextPtr\fR and \fIprevPtr\fR fields point to itself).
  77. To refer
  78. to a list as a whole, the user keeps a pointer to the header; that
  79. header is initialized by a call to \fBList_Init()\fR, which
  80. creates an empty
  81. list given a pointer to a List_Links structure (described below).
  82. .PP
  83. The links are contained in a two-element structure called List_Links.
  84. A list joins List_Links records (that is, each List_Links structure
  85. points to other List_Links structures), but if the List_Links is the
  86. first field within a larger structure, then the larger structures are
  87. effectively linked together as shown in Figure 1.
  88. .if t \{
  89. .bp
  90. .sp 2
  91. .br
  92. .nr g1 999u
  93. .nr g2 499u
  94. .GS C
  95. .nr g3 \n(.f
  96. .nr g4 \n(.s
  97. \0
  98. .sp -1
  99. \D's -1u'\D't 5u'
  100. .sp -1
  101. \D'l 0u 499u'\D'l 999u 0u'\D'l 0u -499u'\D'l -999u 0u'
  102. .sp -1
  103. .ft R
  104. .ps 16
  105. .nr g8 \n(.d
  106. .ds g9 "Figure 1: Structure of a list.
  107. .sp 443u
  108. \h'110u'\&\*(g9
  109. .sp |\n(g8u
  110. \D's 4u'\D't 1u'
  111. .sp -1
  112. .sp 165u
  113. \h'825u'\D'l -166u 0u'
  114. .sp -1
  115. .ft R
  116. .ps 36
  117. .nr g8 \n(.d
  118. .ds g9 "...
  119. .sp 146u
  120. \h'756u'\h-\w\*(g9u/2u\&\*(g9
  121. .sp |\n(g8u
  122. .ft R
  123. .ps 16
  124. .nr g8 \n(.d
  125. .ds g9 "struct
  126. .sp 112u
  127. \h'749u'\h-\w\*(g9u/2u\&\*(g9
  128. .sp |\n(g8u
  129. .ft R
  130. .ps 16
  131. .nr g8 \n(.d
  132. .ds g9 "rest of
  133. .sp 49u
  134. \h'749u'\h-\w\*(g9u/2u\&\*(g9
  135. .sp |\n(g8u
  136. \D's -1u'\D't 3u'
  137. .sp -1
  138. .sp -97u
  139. \h'659u'\D'l 0u 264u'\D'l 166u 0u'\D'l 0u -264u'\D'l -166u 0u'
  140. .sp -1
  141. \D't 1u'
  142. .sp -1
  143. .sp 77u
  144. \h'825u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  145. .sp -1
  146. .ft R
  147. .ps 10
  148. .nr g8 \n(.d
  149. .ds g9 "List_Links
  150. .sp -21u
  151. \h'742u'\h-\w\*(g9u/2u\&\*(g9
  152. .sp |\n(g8u
  153. .ft R
  154. .ps 16
  155. .nr g8 \n(.d
  156. .ds g9 "first elt.
  157. .sp -91u
  158. \h'749u'\h-\w\*(g9u/2u\&\*(g9
  159. .sp |\n(g8u
  160. \D's 4u'
  161. .sp -1
  162. .sp 20u
  163. \h'339u'\D'l -166u 0u'
  164. .sp -1
  165. .ft R
  166. .ps 36
  167. .nr g8 \n(.d
  168. .ds g9 "...
  169. .sp 146u
  170. \h'256u'\h-\w\*(g9u/2u\&\*(g9
  171. .sp |\n(g8u
  172. .ft R
  173. .ps 16
  174. .nr g8 \n(.d
  175. .ds g9 "struct
  176. .sp 112u
  177. \h'249u'\h-\w\*(g9u/2u\&\*(g9
  178. .sp |\n(g8u
  179. .ft R
  180. .ps 16
  181. .nr g8 \n(.d
  182. .ds g9 "rest of
  183. .sp 49u
  184. \h'249u'\h-\w\*(g9u/2u\&\*(g9
  185. .sp |\n(g8u
  186. \D's -1u'\D't 3u'
  187. .sp -1
  188. .sp -97u
  189. \h'173u'\D'l 0u 264u'\D'l 166u 0u'\D'l 0u -264u'\D'l -166u 0u'
  190. .sp -1
  191. .ft R
  192. .ps 36
  193. .nr g8 \n(.d
  194. .ds g9 "...
  195. .sp 28u
  196. \h'61u'\h-\w\*(g9u/2u\&\*(g9
  197. .sp |\n(g8u
  198. .ft R
  199. .ps 36
  200. .nr g8 \n(.d
  201. .ds g9 "...
  202. .sp 77u
  203. \h'61u'\h-\w\*(g9u/2u\&\*(g9
  204. .sp |\n(g8u
  205. .ft R
  206. .ps 36
  207. .nr g8 \n(.d
  208. .ds g9 "...
  209. .sp 77u
  210. \h'950u'\h-\w\*(g9u/2u\&\*(g9
  211. .sp |\n(g8u
  212. .ft R
  213. .ps 36
  214. .nr g8 \n(.d
  215. .ds g9 "...
  216. .sp 35u
  217. \h'950u'\h-\w\*(g9u/2u\&\*(g9
  218. .sp |\n(g8u
  219. \D't 1u'
  220. .sp -1
  221. .sp 77u
  222. \h'825u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  223. .sp -1
  224. \h'902u'\D'l -77u 0u'
  225. .sp -1
  226. \h'659u'\D'l -77u 0u'
  227. .sp -1
  228. \h'582u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  229. .sp -1
  230. \h'416u'\D'l -77u 0u'
  231. .sp -1
  232. \h'96u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  233. .sp -1
  234. \h'173u'\D'l -77u 0u'
  235. .sp -1
  236. .ft R
  237. .ps 10
  238. .nr g8 \n(.d
  239. .ds g9 "List_Links
  240. .sp -21u
  241. \h'256u'\h-\w\*(g9u/2u\&\*(g9
  242. .sp |\n(g8u
  243. .sp -49u
  244. \h'905u'\D'l -9u -6u'\D'l 3u 6u'\D'l -3u 6u'\D'l 9u -6u'
  245. .sp -1
  246. \h'829u'\D'l 76u 0u'
  247. .sp -1
  248. \h'582u'\D'l 77u 0u'
  249. .sp -1
  250. \h'659u'\D'l -10u -6u'\D'l 4u 6u'\D'l -4u 6u'\D'l 10u -6u'
  251. .sp -1
  252. .ft R
  253. .ps 16
  254. .nr g8 \n(.d
  255. .ds g9 "last elt.
  256. .sp -42u
  257. \h'263u'\h-\w\*(g9u/2u\&\*(g9
  258. .sp |\n(g8u
  259. \h'416u'\D'l -10u -6u'\D'l 3u 6u'\D'l -3u 6u'\D'l 10u -6u'
  260. .sp -1
  261. \h'339u'\D'l 77u 0u'
  262. .sp -1
  263. \h'173u'\D'l -10u -6u'\D'l 3u 6u'\D'l -3u 6u'\D'l 10u -6u'
  264. .sp -1
  265. \h'96u'\D'l 77u 0u'
  266. .sp -1
  267. .ft R
  268. .ps 16
  269. .nr g8 \n(.d
  270. .ds g9 "header
  271. .sp -42u
  272. \h'499u'\h-\w\*(g9u/2u\&\*(g9
  273. .sp |\n(g8u
  274. \D't 3u'
  275. .sp -1
  276. .sp -28u
  277. \h'416u'\D'l 0u 97u'\D'l 166u 0u'\D'l 0u -97u'\D'l -166u 0u'
  278. .sp -1
  279. .ft R
  280. .ps 10
  281. .nr g8 \n(.d
  282. .ds g9 "List_Links
  283. .sp 56u
  284. \h'506u'\h-\w\*(g9u/2u\&\*(g9
  285. .sp |\n(g8u
  286. \D't 1u'
  287. .sp -1
  288. .sp 77u
  289. \h'339u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  290. .sp -1
  291. \h'825u'\D'l 10u 6u'\D'l -4u -6u'\D'l 4u -6u'\D'l -10u 6u'
  292. .sp -1
  293. .sp 354u
  294. \D't 3u'\D's -1u'
  295. .br
  296. .ft \n(g3
  297. .ps \n(g4
  298. .GE
  299. .\}
  300. .PP
  301. A typical structure might be something like:
  302.  
  303. .nf
  304.      typedef struct {
  305.                  List_Links links;
  306.                  char ch;
  307.                  int flags;
  308.      } EditChar;
  309. .fi
  310. .LP
  311. It is possible to link structures through List_Links fields that are
  312. not at the beginning of the larger structure, but it is then necessary
  313. to perform an additional pointer indirection to find the beginning of
  314. the larger 
  315. structure, given a pointer to some point within it.  The easiest way to do 
  316. this is to define a structure that contains a List_Links field and a pointer
  317. to the larger structure, such as:
  318. .nf
  319.      typedef struct {
  320.                  List_Links links;
  321.                  LargeStruct *structPtr;
  322.      } LargeStructLink;
  323. .fi
  324. .LP
  325. By including a ``LargeStructLink'' within a ``LargeStruct'' and setting the
  326. structPtr field of the LargeStructLink to point to the LargeStruct
  327. itself, LargeStruct structures may be linked together in a list
  328. that is contained in the middle of the structure rather than the beginning.
  329.  
  330. .SH USAGE
  331. .PP
  332. After a list has been initialized by calling \fBList_Init\fR, elements may
  333. be inserted, deleted, or moved within the list.  
  334. Before an element is inserted in a list for the first time it must
  335. be initialized by calling the routine \fBList_InitElement\fR.  To insert a
  336. List_Links element into a list, \fBList_Insert\fR is called with two
  337. arguments.  The first argument is a pointer to the structure to be
  338. inserted into a list, and the second argument is a pointer to the list
  339. member after which it is to be inserted.  Typically, the following
  340. macros are used to select the insertion point or the destination of a
  341. \fBList_Move\fR:
  342. .IP
  343. .RS
  344. .IP "\(bu \fBLIST_BEFORE\fR(\fIitemPtr\fR)" 30
  345. Insert the element before \fI*itemPtr\fR.
  346. .IP "\(bu \fBLIST_AFTER\fR(\fIitemPtr\fR)" 30
  347. Insert the element after \fI*itemPtr\fR.
  348. .IP "\(bu \fBLIST_ATFRONT\fR(\fIheaderPtr\fR)" 30
  349. Insert the element at the front of the list.
  350. .IP "\(bu \fBLIST_ATREAR\fR(\fIheaderPtr\fR)" 30
  351. Insert the element at the end of the list.
  352. .RE
  353. .VS
  354. .PP
  355. To insert a list into another list, call \fBList_ListInsert\fR with the
  356. header of the list to be inserted and a pointer to the member of the second
  357. list after which the first list is to be inserted.  After calling
  358. \fBList_ListInsert\fP, the header of the first list is no longer valid
  359. and may be destroyed.
  360. .VE
  361. .PP
  362. To remove a structure from a list, call \fBList_Remove\fR with a
  363. pointer to the structure to be removed.  
  364. To move a structure, call \fBList_Move\fR with two arguments: a pointer to
  365. the structure to be moved, and a pointer to the structure after which
  366. it is to be placed.  \fBList_Move\fR(\fIitemPtr\fR, \fIdestPtr\fR) is therefore
  367. equivalent to \fBList_Remove\fR(\fIitemPtr\fR) followed by \fBList_Insert\fR(\fIitemPtr\fR,
  368. \fIdestPtr\fR).
  369.  
  370. .SH ADDITIONAL UTILITIES
  371. .PP
  372. Several other macros are available for the manipulation of List_Links.
  373. \fBLIST_FORALL\fR(\fIheaderPtr\fR, \fIitemPtr\fR) is used to step through each element
  374. in the list pointed to by headerPtr, setting itemPtr to point to each
  375. element in turn.  \fBLIST_FORALL\fR is used typically by casting \fIitemPtr\fR as
  376. a pointer to the entire structure, as in:
  377. .nf
  378.     List_Links *headerPtr;    /* pointer to head of existing list */
  379.     List_Links *itemPtr;    /* place-holder during loop */
  380.     EditChar   *charPtr;    /* pointer to entire EditChar structure */
  381.  
  382.     LIST_FORALL(headerPtr, itemPtr) {
  383.         charPtr = (EditChar *) itemPtr;
  384.         /* operations using charPtr */
  385.     }
  386. .fi
  387. .PP
  388. The following macros may be useful to those who use List_Links at a
  389. ``lower'' level than looping through an entire list:
  390. .RS
  391. .IP "\(bu \fBList_IsEmpty\fR(\fIheaderPtr\fR) " 30
  392. returns TRUE if \fIheaderPtr\fR points to an empty
  393. list.
  394. .IP "\(bu \fBList_IsAtEnd\fR(\fIheaderPtr\fR, \fIitemPtr\fR)" 30
  395. returns TRUE if \fIitemPtr\fR is
  396. past the end of the list; i.e., it points to the header.
  397. .IP "\(bu \fBList_First\fR(\fIheaderPtr\fR) " 30
  398. .IP "\(bu \fBList_Last\fR(\fIheaderPtr\fR) " 30
  399. \fBList_First\fR returns the first member in a list, and
  400. \fBList_Last\fR returns the last member.  If the list is empty,
  401. the header is considered to be the first and last member.
  402. .IP "\(bu \fBList_Prev\fR(\fIitemPtr\fR) " 30
  403. returns a pointer to the member preceding the given
  404. member in its list.
  405. Note:  if the given member is the first element
  406. of the list, \fBList_Prev\fR will return the list header.
  407. .IP "\(bu \fBList_Next\fR(\fIitemPtr\fR)" 30
  408. returns the next
  409. member of the list.
  410. Note:  if the given member is the last element
  411. of the list, \fBList_Next\fR will return the list header.
  412. .RE
  413. .SH KEYWORDS
  414. list, linked, circular, List_Links, data structures
  415. @
  416.  
  417.  
  418. 1.1
  419. log
  420. @Initial revision
  421. @
  422. text
  423. @d1 1
  424. a1 1
  425. ' $Header: /sprite/src/lib/c/list/RCS/List.g,v 1.1 88/12/30 15:20:35 ouster Exp Locker: shirriff $ SPRITE (Berkeley)
  426. d376 3
  427. a378 1
  428. member in its list.  
  429. d382 2
  430. @
  431.